約 2,554,677 件
https://w.atwiki.jp/azounoman/pages/9.html
1130 Alien Security 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1130 解答例 import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int e = sc.nextInt(); boolean[][] adj = new boolean[n][n]; for(int i=0;i n;i++) Arrays.fill(adj[i],false); while(sc.hasNext()){ int p = sc.nextInt(); int q = sc.nextInt(); adj[p][q] = true; } Solver sol = new Solver(n,e,adj); System.out.printf("Put guards in room %d.\r\n",sol.solve()); } } class Solver{ int n; int e; boolean[][] adj; boolean[][] avail; Solver(int n, int e, boolean[][] adj) { this.n = n; this.e = e; this.adj = adj; this.avail = new boolean[n][n]; } public int solve(){ analyzeAvailable(); return nearestPoint(); } private int nearestPoint(){ Queue Integer q = new LinkedList Integer (); boolean[] searched = new boolean[n]; q.offer(e); Arrays.fill(searched,false); searched[e] = true; while(!q.isEmpty()){ int v = q.poll(); if(avail[e][v]) return v; for(int i=0;i n;i++){ if(adj[i][v] !searched[i]){ q.offer(i); searched[i] = true; } } } return -1; } private void analyzeAvailable(){ for(int i=0;i n;i++) Arrays.fill(avail[i],true); for(int k=1;k n;k++) avail[0][k] = false; while(!analyzeAvailableSub()); for(int i=0;i n;i++) avail[i][i] = false; } private boolean analyzeAvailableSub(){ boolean end = true; for(int i=1;i n;i++){ boolean[] availnext = new boolean[n]; Arrays.fill(availnext,false); boolean first = true; for(int p=0;p n;p++){ if(adj[p][i]){ if(first){ for(int k=0;k n;k++){ availnext[k] = avail[p][k]; } first = false; } else{ for(int k=0;k n;k++){ availnext[k] = avail[p][k]; } } } } availnext[i] = true; for(int k=0;k n;k++){ if(avail[i][k]!=availnext[k]) end = false; avail[i][k] = availnext[k]; } } return end; } }
https://w.atwiki.jp/azounoman/pages/52.html
2142 The Balance 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2142 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int a = sc.nextInt(); int b = sc.nextInt(); int d = sc.nextInt(); if(a==0 b==0 d==0) break; int x1,y1,x2,y2,x,y; x1 = d/a; if(a*x1 d) x1++; while((a*x1-d)%b!=0) x1++; y1 = (a*x1-d)/b; y2 = d/b; if(b*y2 d) y2++; while((b*y2-d)%a!=0) y2++; x2 = (b*y2-d)/a; if(x1+y1 x2+y2){ x = x1; y = y1; } else if(x1+y1 x2+y2){ x = x2; y = y2; } else{ if(a*x1+b*y1 a*x2+b*y2){ x = x1; y = y1; } else{ x = x2; y = y2; } } if(a d b d){ int x3,y3; boolean exist; x3 = y3 = -1; exist = false; if(a b){ x3 = 1; while(a*x3 d){ if((d-a*x3)%b==0){ y3 = (d-a*x3)/b; exist = true; break; } x3++; } } else{ y3 = 1; while(b*y3 d){ if((d-b*y3)%a==0){ x3 = (d-b*y3)/a; exist = true; break; } y3++; } } if(exist){ if(x3+y3 x+y){ x = x3; y = y3; } else if(x3+y3==x+y a*x3+b*y3 a*x+b*y){ x = x3; y = y3; } } } System.out.println(x+" "+y); } } }
https://w.atwiki.jp/azounoman/pages/33.html
1923 Fouriers Lines 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1923 解答方針 交差点の数は，直線を平行な直線のグループに分けたときの各グループの直線数がわかれば計算できる．たとえば，問題文の図の状況は (8,4,2,1,1,1) という組で表現することができ，交点数は 0*8+8*4+(8+4)*2+(8+4+2)*1+(8+4+2+1)*1+(8+4+2+1+1)*1=101 と計算できる． 与えられた直線数nに対し，nを自然数の和として表す方法を列挙し，nの自然数の和への分割方法をn本の直線の平行な直線のグループへの分割方法と解釈して，交点数が与えられたものと等しくなるか調べていけばよい．なお，分割される領域数は「直線数+交点数+1」で求めることができる．問題文の「分割される領域数の最大値を求めよ」というのはダミーである． 解答例 import java.util.*; public class Main{ public static void main(String args[]){ int m,n,c; boolean ans; Scanner sc = new Scanner(System.in); c=0; while(true){ n = sc.nextInt(); m = sc.nextInt(); if(n==0) break; c++; Solver sol = new Solver(n,m); ans = sol.solve(); if(ans){ System.out.println("Case "+c+" "+n+" lines with exactly "+m+" crossings can cut the plane into "+(n+m+1)+" pieces at most."); } else{ System.out.println("Case "+c+" "+n+" lines cannot make exactly "+m+" crossings."); } } } } class Solver{ int n,m; Solver(int n0,int m0){ n = n0; m = m0; } public boolean solve(){ return solveMain(n,m,0,n); } private boolean solveMain(int n,int m,int l,int a){ if(n==0){ if(m==0){ return true; } else{ return false; } } if(a==1){ if(m==n*(2*l+n-1)/2){ return true; } else{ return false; } } //cut int q = n/a; if(l*n m){ return false; } if(n*(2*l+n-1)/2 m){ return false; } //next boolean ans = false; for(int i=1;i =a;i++){ boolean tmp = solveMain(n-i,m-l*i,l+i,i); if(tmp){ ans = true; break; } } return ans; } }
https://w.atwiki.jp/pkujapan/
PKU 日本語化計画 このwikiは、PKU(PKU OnlineJudge)の問題を日本語に翻訳するwikiです。 中国語が分かる方、どうかご協力お願いします。 wikiを移動することになりました。移動先は、PKU Wikiです。ここも残しておきますが、更新はないと思われます。 このwikiのルールは、ここをご覧ください。 翻訳済みの問題は、ここをご覧ください。 総合 - 本日 - 昨日 - コメントをつけるといろいろと便利 -- tozangezan (2009-04-30 06 15 24) 深さ優先探索ってなんなんだ？ -- tozangezan (2009-04-30 21 40 14) 名前 コメント
https://w.atwiki.jp/azounoman/pages/27.html
1602 Zip 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1602 解答例 import java.util.*; public class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); String mode = sc.next(); if(mode.equals("A")){ int n = sc.nextInt(); char[] str = new char[n]; str = sc.next().toCharArray(); if(n==1){ System.out.println(str); System.out.println(1); return; } // n 1 ZipString[] zs = new ZipString[n]; for(int i=0;i n;i++){ char head = str[i]; char tail = str[(i+n-1)%n]; ZipString z = new ZipString(i,head,tail); zs[i] = z; } Arrays.sort(zs); char[] zstr = new char[n]; int p = -1; for(int i=0;i n;i++){ zstr[i] = zs[i].tail; if(zs[i].k==1) p = i; } System.out.println(zstr); System.out.println(p+1); } else if(mode.equals("B")){ int n = sc.nextInt(); char[] zstr = new char[n]; zstr = sc.next().toCharArray(); int p = sc.nextInt()-1; char[] zstr_next = new char[n]; for(int i=0;i n;i++) zstr_next[i] = zstr[i]; Arrays.sort(zstr_next); int[] m = new int[26]; Arrays.fill(m,-1); for(int i=0;i n;i++) m[(zstr_next[i])- a ] = i; char[] str = new char[n]; int a = -1; for(int i=0;i n;i++){ if(zstr_next[i]==zstr[p]){ a = i; break; } } str[n-1] = zstr[a]; for(int i=n-1;i 0;i--){ int k = m[str[i]- a ]; str[i-1] = zstr[k]; m[str[i]- a ] = k-1; } System.out.println(str); } else throw new Exception(); } } class ZipString implements Comparable ZipString { int k; char head; char tail; ZipString(int k, char head,char tail) { this.k = k; this.head = head; this.tail = tail; } public boolean equals(Object o){ ZipString z = (ZipString)o; return this.head==z.head; } public int compareTo(ZipString z){ return this.head-z.head; } }
https://w.atwiki.jp/azounoman/pages/38.html
2031 Building a Space Station 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2031 解答方針 最小全域木．今回はKruskalのアルゴリズムで解いた． 解答例 import java.io.*; import java.util.*; import java.text.*; public class Main{ public static void main(String[] args)throws IOException{ Scanner sc = new Scanner(System.in); DecimalFormat formatter = new DecimalFormat("#0.000"); int n = sc.nextInt(); while(n!=0){ double data[][] = new double[n][4]; for(int i=0;i n;i++){ data[i][0] = sc.nextDouble(); data[i][1] = sc.nextDouble(); data[i][2] = sc.nextDouble(); data[i][3] = sc.nextDouble(); } Solver s = new Solver(n,data); double ans = s.solve(); System.out.println(formatter.format(ans)); n = sc.nextInt(); } } } class Solver{ int size; int connected[];//expression of MF-SET PriorityQueue Edge q; Solver(int n,double data[][]){ size = n; connected = new int[size]; q = new PriorityQueue Edge (); for(int i=0;i n;i++){ for(int j=i+1;j n;j++){ double elen = edgeLength(data[i],data[j]); Edge e = new Edge(i,j,elen); q.offer(e); } } for(int i=0;i n;i++) connected[i] = i; } public double solve(){ double corlen; corlen = 0; //Kruskal s algorithm while(!q.isEmpty()){ Edge e = q.poll(); int i = e.p1; int j = e.p2; if(connected[i]!=connected[j]){ merge(i,j); corlen += e.length; } } return corlen; } //MERGE OF MF-SET private void merge(int i,int j){ int m1 = connected[i]; int m2 = connected[j]; for(int k=0;k size;k++){ if(connected[k]==m2) connected[k] = m1; } } private double edgeLength(double d1[],double d2[]){ double dx = d1[0]-d2[0]; double dy = d1[1]-d2[1]; double dz = d1[2]-d2[2]; double dist = Math.sqrt(dx*dx+dy*dy+dz*dz); double prelen = dist - (d1[3]+d2[3]); if(prelen =0.0) return prelen; else return 0.0; } } class Edge implements Comparable Edge { int p1; int p2; double length; Edge(int i,int j,double l){ p1 = i; p2 = j; length = l; } public int compareTo(Edge e){ if(length e.length) return 1; else if(length==e.length) return 0; else return -1; } }
https://w.atwiki.jp/azounoman/pages/24.html
1458 Common Subesequence 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1458 解答方針 最長共通部分列問題． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String s1 = sc.next(); String s2 = sc.next(); Solver sol = new Solver(s1,s2); System.out.println(sol.solve()); } } } class Solver{ String s1; String s2; Solver(String is1,String is2){ s1 = is1; s2 = is2; } public int solve(){ int len1 = s1.length(); int len2 = s2.length(); int[][] table = new int[len1+1][len2+1]; for(int i=0;i =len1;i++) table[i][0] = 0; for(int j=0;j =len2;j++) table[0][j] = 0; for(int k=1;k =Math.min(len1,len2);k++){ if(s1.charAt(k-1)==s2.charAt(k-1)){ table[k][k] = max3(table[k-1][k-1]+1,table[k][k-1],table[k-1][k]); } else{ table[k][k] = max3(table[k-1][k-1],table[k][k-1],table[k-1][k]); } for(int i=k+1;i =len1;i++){ if(s1.charAt(i-1)==s2.charAt(k-1)){ table[i][k] = max3(table[i-1][k-1]+1,table[i][k-1],table[i-1][k]); } else{ table[i][k] = max3(table[i-1][k-1],table[i][k-1],table[i-1][k]); } } for(int j=k+1;j =len2;j++){ if(s1.charAt(k-1)==s2.charAt(j-1)){ table[k][j] = max3(table[k-1][j-1]+1,table[k][j-1],table[k-1][j]); } else{ table[k][j] = max3(table[k-1][j-1],table[k][j-1],table[k-1][j]); } } } return table[len1][len2]; } public static int max3(int x,int y,int z){ return Math.max(x,Math.max(y,z)); } }
https://w.atwiki.jp/azounoman/pages/7.html
1128 Frame Stacking 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1128 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int h = sc.nextInt(); int w = sc.nextInt(); char[][] table = new char[h][w]; for(int i=0;i h;i++) table[i] = sc.next().toCharArray(); Solver sol = new Solver(h,w,table); sol.printSolution(); } } } class Solver{ int h; int w; char[][] table; int letternum; char[] letterset; HashMap Character,Integer dict; boolean[][] less; Solver(int h, int w, char[][] table) { this.h = h; this.w = w; this.table = table; makeLetterSet(); } public void printSolution(){ makeLessTable(); char[] output = new char[letternum]; boolean[] used = new boolean[letternum]; Arrays.fill(used,false); printSolution(0,output,used); } private void printSolution(int k,char[] output,boolean[] used){ if(k==letternum) System.out.println(output); for(int i=0;i letternum;i++){ if(used[i]) continue; output[k] = letterset[i]; boolean cont = false; int l = dict.get(output[k]); for(int j=0;j k;j++){ int m = dict.get(output[j]); if(less[l][m]){ cont = true; break; } } if(cont) continue; used[i] = true; printSolution(k+1,output,used); used[i] = false; } } private void makeLessTable(){ less = new boolean[letternum][letternum]; for(int i=0;i letternum;i++) Arrays.fill(less[i],false); for(int k=0;k letternum;k++){ char c = letterset[k]; int hmin = h; int hmax = -1; int wmin = w; int wmax = -1; for(int i=0;i h;i++){ for(int j=0;j w;j++){ if(table[i][j]==c){ if(i hmin) hmin = i; if(i hmax) hmax = i; if(j wmin) wmin = j; if(j wmax) wmax = j; } } } for(int i=hmin;i =hmax;i++){ if(table[i][wmin]!=c){ char d = table[i][wmin]; int l = dict.get(d); less[k][l] = true; } if(table[i][wmax]!=c){ char d = table[i][wmax]; int l = dict.get(d); less[k][l] = true; } } for(int j=wmin;j =wmax;j++){ if(table[hmin][j]!=c){ char d = table[hmin][j]; int l = dict.get(d); less[k][l] = true; } if(table[hmax][j]!=c){ char d = table[hmax][j]; int l = dict.get(d); less[k][l] = true; } } } } private void makeLetterSet(){ boolean[] find = new boolean[26]; Arrays.fill(find,false); for(int i=0;i h;i++){ for(int j=0;j w;j++){ if(table[i][j]== . ) continue; int c = table[i][j] - A ; if(!find[c]) find[c] = true; } } int cnt = 0; for(int i=0;i 26;i++){ if(find[i]) cnt++; } letternum = cnt; letterset = new char[letternum]; dict = new HashMap Character,Integer (); cnt = 0; for(int i=0;i 26;i++){ if(find[i]){ letterset[cnt] = (char)( A +i); dict.put(letterset[cnt],cnt); cnt++; } } } }
https://w.atwiki.jp/azounoman/pages/8.html
1129 Channel Allocation 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1129 注意 隣接関係は対称的になっていると注釈がありますが，入力は必ずしもそうなっていません．AがBに隣接しているという入力があれば，BがAに隣接しているという情報を自分で補ってやる必要があります． 解答方針 平面グラフであるという注釈があるので，四色定理により必要なチャンネル数は4以下になることを利用します． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; boolean[][] adj = new boolean[n][n]; for(int i=0;i n;i++) Arrays.fill(adj[i],false); for(int i=0;i n;i++){ String line = sc.next(); for(int j=2;j line.length();j++){ int c = line.charAt(j)- A ; adj[i][c] = true; adj[c][i] = true; } } if(colorable1(adj,n)) System.out.println("1 channel needed."); else if(colorable2(adj,n)) System.out.println("2 channels needed."); else if(colorable3(adj,n)) System.out.println("3 channels needed."); else System.out.println("4 channels needed."); } } public static boolean colorable1(boolean[][] adj,int n){ for(int i=0;i n;i++){ for(int j=i+1;j n;j++){ if(adj[i][j]) return false; } } return true; } public static boolean colorable2(boolean[][] adj,int n){ int[] col = new int[n]; return colorable2(adj,n,col,0); } public static boolean colorable2(boolean[][] adj,int n,int[] col,int k){ if(k==n) return true; col[k] = 0; boolean cont = false; for(int i=0;i k;i++){ if(adj[i][k] col[i]==col[k]){ cont = true; break; } } if(!cont){ if(colorable2(adj,n,col,k+1)) return true; } col[k] = 1; cont = false; for(int i=0;i k;i++){ if(adj[i][k] col[i]==col[k]){ cont = true; break; } } if(!cont){ if(colorable2(adj,n,col,k+1)) return true; } return false; } public static boolean colorable3(boolean[][] adj,int n){ int[] col = new int[n]; return colorable3(adj,n,col,0); } public static boolean colorable3(boolean[][] adj,int n,int[] col,int k){ if(k==n) return true; col[k] = 0; boolean cont = false; for(int i=0;i k;i++){ if(adj[i][k] col[i]==col[k]){ cont = true; break; } } if(!cont){ if(colorable3(adj,n,col,k+1)) return true; } col[k] = 1; cont = false; for(int i=0;i k;i++){ if(adj[i][k] col[i]==col[k]){ cont = true; break; } } if(!cont){ if(colorable3(adj,n,col,k+1)) return true; } col[k] = 2; cont = false; for(int i=0;i k;i++){ if(adj[i][k] col[i]==col[k]){ cont = true; break; } } if(!cont){ if(colorable3(adj,n,col,k+1)) return true; } return false; } }
https://w.atwiki.jp/azounoman/pages/29.html
1845 Sumdiv 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1845 解答方針 いくつかの数学的事実を用いる． p1^r1 p2^r2 ... pn^rn の約数の和は (1 + p1 + ... + p1^r1)(1 + p2 + ... + p2^r2) ... (1 + pn + ... + pn^rn) とかける． フェルマーの小定理により a^(p-1) = 1 (mod p) がなりたつ． さらに， 1 + a + a^2 + ... + a^(p-2) = | when a = 0 then 1 | when a = 1 then p-1 | otherwise then 0 (mod p) がなりたつ． 解答例 import java.util.*; public class Main { final static int M = 9901; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] prime = new int[3000]; makePrimeTable(prime); // prime[2999] = 27449 int a = sc.nextInt(); int b = sc.nextInt(); int ans; if(a!=0){ Vector IntPair v = new Vector IntPair (); factorization(a,v,prime); for(IntPair p v){ p.fst %= M; p.snd *= b; } ans = 1; for(IntPair p v){ int pa = p.fst; int pb = p.snd; // pb = k*(M-1) + r; int k = pb/(M-1); k %= M; int r = pb%(M-1); int product; if(pa==0) product = 1; else if(pa==1) product = (M-1)*k + expsum(pa,r); else product = expsum(pa,r); product %= M; ans *= product; ans %= M; } } else ans = 0; System.out.println(ans); } private static int expsum(int x,int n){ int ret = 1; int add = 1; for(int i=1;i =n;i++){ add *= x; add %= M; ret += add; ret %= M; } return ret; } private static void factorization(int x,Vector IntPair v,int[] prime){ for(int i=0;/*i prime.length */prime[i]*prime[i] =x;i++){ int cnt = 0; while(x%prime[i]==0){ x /= prime[i]; cnt++; } v.add(new IntPair(prime[i],cnt)); if(x==1) break; } if(x!=1) v.add(new IntPair(x,1)); } private static void makePrimeTable(int[] prime){ int x = 2; int cnt = 0; while(cnt prime.length){ boolean divided = false; for(int i=0;i cnt prime[i]*prime[i] =x;i++){ if(x%prime[i]==0){ divided = true; break; } } if(!divided){ prime[cnt] = x; cnt++; } x++; } } } class IntPair{ int fst; int snd; public IntPair(int fst, int snd) { this.fst = fst; this.snd = snd; } }